// 题目描述
// 给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印 出次数前k名的字符串。
// [要求]
// 如果strArr长度为N，时间复杂度请达到O(Nlog⁡K)O(N \log K)O(NlogK)

// 输出K行，每行有一个字符串和一个整数（字符串表示）。
// 你需要按照出现出现次数由大到小输出，若出现次数相同时字符串字典序较小的优先输出

/**
 * return topK string
 * @param strings string字符串一维数组 strings
 * @param stringsLen int strings数组长度
 * @param k int整型 the k
 * @return string字符串二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
typedef struct info {
    char *strp;
    int cnt;
} info_t;

// 比较字典序, 要操作字符串
int cmp_dictionary(const void *a, const void *b) {
    return strcmp(*(char **)a, *(char **)b); // 传入的是&strings[i]
}
int cmp_down(const void *a, const void *b) {
    info_t *left = (info_t *)a, *right = (info_t *)b;
    if (left->cnt == right->cnt)
        return strcmp(left->strp, right->strp);
    return right->cnt - left->cnt;
}

char* ** topKstrings(char** strings, int stringsLen, int k, int* returnSize, int** returnColumnSizes ) {
    info_t record[stringsLen];
    // 先对字符串排序，方便统计与记录
    qsort(strings, stringsLen, sizeof(char *), cmp_dictionary);
    
    int slow = 0, fast = 0;
    while (fast < stringsLen) {
        // string[fast]与record末尾元素比较
        if (slow == 0 || strcmp(record[slow - 1].strp, strings[fast]) != 0) {
            record[slow].cnt = 1;
            record[slow++].strp = strings[fast];
        }
        else if (strcmp(record[slow - 1].strp, strings[fast]) == 0) {
            record[slow - 1].cnt++;
        }
        fast++;
    }
    qsort(record, slow, sizeof(info_t), cmp_down);

    // 保存结果
    char ***res =(char ***)malloc(sizeof(char **) * k);
    *returnColumnSizes = (int *)malloc(sizeof(int) * k);
    char *cnt_str = (char *)malloc(sizeof(char)*100);
    for (int i = 0; i < k; i++) {
        (*returnColumnSizes)[i] = 2;
        res[i] = (char **)malloc(sizeof(char *) * 2);
        
        res[i][0] = record[i].strp;
//         itoa(record[i].cnt, cnt_str);
        sprintf(cnt_str,"%d",record[i].cnt);
        res[i][1] = (char *)malloc(sizeof(char) * (strlen(cnt_str) + 1));
        strcpy(res[i][1], cnt_str);
    }
    *returnSize = k;
    free(cnt_str);
    return res;
}


















